class Concept:
    def __init__(self, extent, intent):
        self.extent = extent  # 外延: 对象集合
        self.intent = intent  # 内涵: 属性集合
        self.parents = set()  # 父概念
        self.children = set()  # 子概念

    def __repr__(self):
        return "Concept(Extent: {}, Intent: {})".format(self.extent, self.intent)

    def __eq__(self, other):
        return self.extent == other.extent and self.intent == other.intent

    def __hash__(self):
        return hash(frozenset(self.extent)) ^ hash(frozenset(self.intent))
class ConceptLattice:
    def __init__(self):
        self.concepts = set()  # 存储概念的集合
        self.concept_dict = {}  # 查找概念，键为内涵，值为Concept实例

    def add(self, concept):
        self.concepts.add(concept)
        self.concept_dict[frozenset(concept.intent)] = concept

    def find(self, intent):
        return self.concept_dict.get(frozenset(intent), None)

    def remove(self, concept):
        self.concepts.remove(concept)
        del self.concept_dict[frozenset(concept.intent)]
def compute_closure(attribute, I, G):
    closure_extent = set(G)  # 初始时，外延闭包为所有对象

    for m in attribute:
        # 保留那些与所有属性 m 相关联的对象 g
        closure_extent = {g for g in closure_extent if (g, m) in I}

    return closure_extent


def attribute_closure(A, I, M):
    closure = set()

    # 遍历属性集合 M 中的每个属性
    for m in M:
        # 如果 A 中的所有对象都和属性 m 相关联（即 gIm），则将属性 m 加入闭包
        if all((g, m) in I for g in A):
            closure.add(m)

    return closure
def get_closure_concept(Y, generator, L):
    existing_concept = L.find(Y)
    if existing_concept is not None:
        return existing_concept

    closure_extent = set()
    for attribute in Y:
        attribute_closure = compute_closure(attribute, I, G)
        if not closure_extent:
            closure_extent = attribute_closure
        else:
            closure_extent &= attribute_closure  # 求交集

    closure_intent = set(Y)
    generator_intent_set = set(generator.intent)

    for m in generator_intent_set - set(Y):
        if closure_extent <= compute_closure(m, I, G):
            closure_intent |= {m}  # 求并集

    return L.find(closure_intent)

def fast_add_intent(Y, generator, L):
    # 获取规范生成元
    generator = get_closure_concept(Y, generator, L)

    if generator == Y:
        return generator
    generator_parents =generator.Parents
    new_parents = None
    for candidate in generator_parents:
        if candidate.extent is not Y:
            candidate = fast_add_intent(candidate.intent & Y, candidate, L)
            break
        new_parents.add(candidate)
    new_concept = Concept(generator.extent, Y)
    L |= {new_concept}
    for parent in new_parents:
        isTrueParent = True
        children = parent.children
        for child in children:
            if child.intent < Y:
                isTrueParent = False
                break
        if isTrueParent:
            remove_links(generator, parent)
            set_links(new_concept, parent)
    set_links(generator, new_concept)
    return new_concept


def remove_links(generator, parent):
    parent.children.discard(generator)
    generator.parents.discard(parent)


def set_links(generator, parent):
    generator.parents.add(parent)
    parent.children.add(generator)


def create_lattice_incrementally(G, M, I):
    bottom_concept = Concept(set(), M)
    L = ConceptLattice()
    L.add(bottom_concept)

    for g in G:
        object_concept = fast_add_intent(compute_closure(attribute_closure(g,I, M),I, G), bottom_concept, L)
        add_to_extents(g, object_concept, L)

    return L

def add_to_extents(object, object_concept, L):
    if object_concept is not None:
        object_concept.extent.add(object)
        for parent in object_concept.parents:
            add_to_extents(object, parent, L)
    else:
        print("Error: Object concept is None for object", object)


def read_file(filename):
    with open(filename, 'r') as f:
        first_line = f.readline().strip()
        num_objects, num_attributes = map(int, first_line.split(','))
        data = [list(map(int, line.strip().split(','))) for line in f]
    return num_objects, num_attributes, data


def build_formal_context(num_objects, num_attributes, data):
    M = [chr(ord('a') + i) for i in range(num_objects)]  # 对象集合
    G = [str(j + 1) for j in range(num_attributes)]  # 属性集合

    I = {(G[i], M[j]) for i in range(num_objects) for j in range(num_attributes) if data[i][j] == 1}

    return G, M, I


filename = "../txt/demo6.txt"
num_objects, num_attributes, data = read_file(filename)

# 构建形式背景 K = (G, M, I)
G, M, I = build_formal_context(num_objects, num_attributes, data)

# 构建概念格
L = create_lattice_incrementally(G, M, I)

# 输出最终的概念格
for concept in L.concepts:
    print(concept)
